#pragma once
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::swap;
class sort
{
private:
  int a[10];

public:
  sort();
  void init();     //初始化数组
  void show();     //遍历数组
  void 冒泡排序(); //冒泡排序
  void 快速排序(int left, int right);
  void 选择排序();
  void 插入排序();
  void 计数排序();
  void 希尔排序();
  void 桶排序();
};
sort::sort()
{
  int 随机数;
  srand(time(0));
  for (int i = 0; i < 10; i++)
  {
    随机数 = rand() % 100;
    a[i] = 随机数;
  }
}
void sort::show()
{
  for (int i = 0; i < 10; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
}
void sort::init()
{
  int 随机数;
  srand(time(0));
  for (int i = 0; i < 10; i++)
  {
    随机数 = rand() % 100;
    a[i] = 随机数;
  }
  show();
}

// 很形象直观
void sort::冒泡排序()
{
  for (int i = 0; i < 10 - 1; i++)
  {
    for (int j = 0; j < 10 - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        swap(a[j], a[j + 1]);
      }
    }
  }
  cout << "冒泡排序完成" << endl;
}
void sort::快速排序(int left, int right)
{
  int temp; //存取基准数
  int t;
  int initial = left;
  int end = right;
  temp = a[left]; //先选取数组的第一个元素作为基准数
  if (left > right)
  {
    return;
  }
  while (left != right)
  {
    while (a[right] >= temp && left < right)
    {
      right--;
    }
    while (a[left] <= temp && left < right)
    {
      left++;
    }
    if (left < right)
    {
      t = a[right];
      a[right] = a[left];
      a[left] = t;
    }
  }
  a[initial] = a[left];
  a[left] = temp;
  快速排序(initial, left - 1);
  快速排序(left + 1, end);
}
void sort::选择排序() //每次选择最小的元素放到数组第一位
{
  int min;
  int k = 0; //k是每做一次循环把数组的首尾重新设置
  int temp;  //记录数组中最小的元素在哪一位
  for (int i = 0; i < 10 - 1; i++)
  {

    for (int j = k; j < 10; j++)
    {
      int min = a[k];
      temp = k;
      if (min > a[j])
      {
        temp = j;
      }
      min = min < a[j] ? min : a[j];
      swap(a[k], a[temp]);
    }
    k++;
  }
  cout << "选择排序完成" << endl;
}
void sort::插入排序() //选择一位按照值的大小插入到有序的序列中
{
  //默认升序排列
  int i, j;
  for (i = 1; i < 10; i++)
  {
    for (j = i - 1; j >= 0; j--)
    {
      if (a[i] > a[j])
      {
        break;
      }
    }
    int temp = a[i];
    for (int k = i - 1; k > j; k--)
    {
      a[k + 1] = a[k];
    }
    a[j + 1] = temp;
  }
  cout << "插入排序完成" << endl;
}
void sort::计数排序() //对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接吧x放到它在输出数组中的位置上了。
                      //例如，如果有17个元素小于x, 则x就应该在第18个输出位置上。
{
  int b[10]; //暂存数组
  int temp;  //暂存目前需要分析的数据值
  int count; //统计有多少数比temp小
  for (int i = 0; i < 10; i++)
  {
    temp = a[i]; //开始着手处理数组的某一元素
    count = 0;
    for (int j = 0; j < 10; j++)
    {
      if (temp > a[j])
      {
        count++;
      }
    }
    b[count] = temp;
  }
  for (int i = 0; i < 10; i++)
  {
    a[i] = b[i];
  }
  cout << "计数排序完成" << endl;
}
void sort::希尔排序()
{
  int gap;
  for (gap = 3; gap > 0; gap--)
  {
    for (int i = 0; i < gap; i++)
    {
      for (int j = i + gap; j < 10; j = j + gap)
      {
        if (a[j] < a[j - gap])
        {
          int temp = a[j];
          int k = j - gap;
          while (k >= 0 && a[k] > temp)
          {
            a[k + gap] = a[k];
            k = k - gap;
          }
          a[k + gap] = temp;
        }
      }
    }
  }
  cout << "希尔排序完成" << endl;
}
void sort::桶排序() //新建立一个长度等于数组最大值+1的数组，遍历数组记录这些值的出现次数，然后输出。
{
  int max; //计算最大值
  max = a[0];
  int temp = 0; //目前数组a正在处理的元素位置
  for (int i = 0; i < 10; i++)
  {
    max = max > a[i] ? max : a[i];
  }
  int *b = new int[max + 1]; //动态数组
  for (int i = 0; i < max + 1; i++)
  {
    b[i] = 0; //初始化数组，0表示数组a中值为下标i的数据出现次数为0
  }
  for (int i = 0; i < 10; i++)
  {
    b[a[i]]++; //b的下标a[i]就是a出现的元素在整个数组b的位置。
  }
  for (int i = 0; i < max + 1; i++)
  {
    while (b[i] != 0)
    {
      a[temp] = i; //注意不是b[i]，因为下标才是储存的值。
      b[i]--;      //万一有b[i]大于1的情况，就是说数组中有重复值
      temp++;
    }
  }

  delete[] b;
  cout << "桶排序完成" << endl;
}